package class01.sort;

/**
 * @Auther: xw
 * @Create: 2022/3/2 15:02
 * @Description: 选择排序  冒泡排序
 */
public class SelectSort {
    public static void main(String[] args) {

        int[] num = {7,9,5,8,1,5,2,6,1,10,66,0};
        printArray(num);
        insertSort2(num);
        printArray(num);

    }

    /**
     * 每次选出最小的放在对应位置，依次循环  ，每次循环结束不用管第i-1位
     * @param num
     */
    public static void selectSort(int[] num){

         if(null == num || num.length < 2){
             return;
         }
        int length = num.length;
        for (int i = 0; i < length; i++) {
            int arraysMinIndex = i;
            for (int j = i+1; j < length; j++) {
                arraysMinIndex = num[j] < num[arraysMinIndex] ? j : arraysMinIndex;
            }
            swapArray(num,i,arraysMinIndex);
        }
    }

    /**
     * 冒泡排序 两两交换 小的前移动  每次循环结束不用管最后一位
     * @param num
     */
    public static void bubbleSort(int[] num){
        if(null == num || num.length < 2){
            return;
        }
        int length = num.length;
        for(int end = length -1 ; end >= 0; end--){
            for (int second = 1; second <= end; second++) {
                if(num[second-1] > num[second]){
                    swapArray(num,second-1,second);
                }
            }
        }
    }

    /**
     * 插入排序 每次向后移动一个位置，与前一比较，小于前一位就交换
     * @param num
     */
    public static void insertSort1(int[] num ){
        if(null == num || num.length < 2){
            return;
        }
        int length = num.length;
            for (int end = 1; end < length; end++) {
           int index = end;
           while(index - 1 >= 0 && num[index -1] > num[index]){
               swapArray(num,index-1,index);
               index--;
           }

        }
    }
    public static void insertSort2(int[] num ){
        if(null == num || num.length < 2){
            return;
        }
        int length = num.length;
        for (int end = 1; end< length; end++) {
           for(int pre =end-1;pre>=0&& num[pre] > num[pre+1];pre-- ){
               swapArray(num,pre,pre+1);
           }
        }
    }

    public static void swapArray(int[] num,int i,int j){
        int temp = num[j];
        num[j]=num[i];
        num[i]= temp;
    }
    public static void printArray(int[] num){
        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i] + " ");

        }
        System.out.println();
    }
}
